//
// Created by cyy on 2020/10/18.
//

/*****************************************************************************
文件名： scl.h
实现文件： scl.cpp

本文件定义了四个命名空间：
+ cn_sunist_prevdefine
+ cn_sunist_datastructure_algorithm
+ cn_sunist_datastructure_prevlib
+ cn_sunist_datastructure_library

其中，cn_sunist_datastructure_library是主要命名空间，主要类定义都在其中。
包含以下内容：

+ 线性结构
ArrayList<ElemType>: 范型顺序表
ArrayQueue<ElemType>: 范型顺序队列
ArrayStack<ElemType>: 范型顺序栈
LinearSet<ElemType>: 范型线性集合
LinkedArrayList<ElemType>: 范型改进块状链表
LinkedList<ElemType>: 范型链表
LinkedQueue<ElemType>: 范型链队列
LinkedStack<ElemType>: 范型链栈
线性结构参考链接： https://zhuanlan.zhihu.com/p/30343791

+ 树状结构
BinaryTree<ElemType>: 范型二叉树
BinarySearchTree<ElemType>: 范型二叉搜索树
AVLTree<ElemType>: 范型自平衡二叉搜索树
RBTree<ElemType>: 范型红黑树
BTree<ElemType>: 范型多路搜索树
BpTree<ElemType>: 范型B+树
BXTree<ElemType>: 范型B*树
TireTree<ElemType>: 范型字典树
树状结构参考链接： https://blog.csdn.net/smilejiasmile/article/details/82843278

+ 图/网结构

*****************************************************************************/

#ifndef DATA_STRUCTURE_EXPERIMENT_SCL_H
#define DATA_STRUCTURE_EXPERIMENT_SCL_H

// ========================= CN_SUNIST_PREVDEFINE ========================= //
// ====================== CN_SUNIST_PREVDEFINE_START ====================== //
/**
 * @Lastedit Sunist Chan
 * @Createdate 2020-10-08
 * @Authors Sunist Chan, CALC.
 * @Description The defines, enums in sunist_chan_datastructure_library
 * 
 * 这是scl库的预定义命名空间，定义了scl库的枚举类型和预编译语句
 */
namespace cn_sunist_prevdefine {

    /**
     * @brief 这是scl库的方法张泰返回值
     */
    enum Status {
        success, // 运行成功
        overflow, // 指针越界
        notfound, // 元素未找到
        argumenterror // 参数错误
    };

    /**
     * @brief 这是scl库的排序模式
     */
    enum SortMode {
        stlsort, // stl库排序
        quicksort, // 快速排序
        bubblesort, // 冒泡排序
        shellsort, // 希尔排序
        insertsort, // 插入排序
        selectsort // 选择排序
    };

    #define scl cn_sunist_datastructure_library
}
using namespace cn_sunist_prevdefine;
// ======================= CN_SUNIST_PREVDEFINE_END ======================= //










// ========================== CN_SUNIST_ALGORITHM ========================= //
// ======================= CN_SUNIST_ALGORITHM_START ====================== //
/**
 * @Lastedit Sunist Chan
 * @Createdate 2020-10-08
 * @Authors Sunist Chan, CALC.
 * @Description The basic algortihm in sunist_chan_datastructure_library
 * 
 * 这是scl库的算法命名空间，包含基础比较方法与排序方法
 */
namespace cn_sunist_datastructure_algorithm {
    /**
     * @brief Compare wgether the elements are the same
     * @param a,b two elements
     * @return Comparision results ,identical is true
    */
    template<typename ElemType> bool memcompare(ElemType a, ElemType b);

    /**
     * @brief Sort arrays
     * @param start where sorts starts
     * @param end where sorts end
     * @param arr array to sort
     * @param Judge whether the ElementType is the same,the same is true
    */
    template<typename ElemType> void quick_sort(int start, int end, ElemType* arr, bool compare(ElemType, ElemType));

    /**
     * @brief the LCS algorithm, which to calculate the Longest Common Subsequence of the two string a and b
     * @param a one string
     * @param b one string
     * @return the length of the Longest Common Subsequence
     */
    int LCS_Length(std::string a, std::string b);

    /**
     * @brief the LCS algorithm, which to calculate the Longest Common Subsequence of the two string a and b
     * @param a one string
     * @param b one string
     * @return the Longest Common Subsequence string
     */
    std::string LCS_String(std::string a, std::string b);
}
// ======================== CN_SUNIST_ALGORITHM_END ======================= //










// ==================== CN_SUNIST_DATASTRUCTURE_PREVLIB =================== //
// ================= CN_SUNIST_DATASTRUCTURE_PREVLIB_START ================ //
/**
 * @Lastedit Sunist Chan
 * @Createdate 2020-10-08
 * @Authors Sunist Chan, CALC.
 * @Description The basic classes which scl will used in sunist_chan_datastructure_library
 * 
 * 这是scl库的预定义类型命名空间，所有正式类需要的前置类都在本命名空间内
 */
namespace cn_sunist_datastructure_prevlib {
    template<typename ElemType>
    class LinkedListNode {
    private:
        ElemType innerData;

    public:
        LinkedListNode<ElemType> *nextNode;
        LinkedListNode<ElemType> *prevNode;

        /**
         * @brief the constructor of LinkedListNode 
         */
        LinkedListNode<ElemType> ();

        /**
         * @brief the constructor of LinkedListNode
         * @param data the defalut data in the LinkedListNode
         */
        LinkedListNode<ElemType> (ElemType data);

        /**
         * @brief get the inside data of LinkedListNode
         * @return the inside data of LinkedListNode
         */
        ElemType& Data();
    };

    template<typename ElemType> 
    class LinkedArrayListNode {
    private:
        ElemType* innerData;
        int defineSize;
        int startIndex;
        int usedSize;

    public:
        LinkedArrayListNode<ElemType>* nextNode;
        LinkedArrayListNode<ElemType>* prevNode;

        /**
         * @brief the constructor of LinkedArrayListNode
         * @param size the defaultsize of the data zone of LinkedArrayListNode
         */
        LinkedArrayListNode<ElemType>(int size=10);

        /**
         * @brief the copy constructor of LinkedArrayListNode
         * @param listNode another LinkedArrayListNode
         */
        LinkedArrayListNode<ElemType>(const LinkedArrayListNode<ElemType>& listNode);

        /**
         * @brief find the DefineSize
         * @return the DefineSize
        */
        int DefineSize();

        /**
         * @brief find the UsedSize
         * @return the UsedSize
        */
        int UsedSize();

        /**
         * @brief find the location of the element
         * @param data the element to find
         * @param compare a function of comparison
         * @return the subscript of the element to find
        */
        int Locate(ElemType data, bool compare(ElemType));

        /**
         * @brief judge whether the LinkedArrayListNode is empty
         * @return if UsedSize equals zero, return true
        */
        bool Empty();

        /**
         * @brief judge whether the LinkedArrayListNode is filled
         * @param if the usedSize equals the defineSize, return true
        */
        bool Filled();

        /**
         * @brief Initializing a LinkedArrayListNode
         * @param data The data put into the LinkedArrayListNode
         * @return the Initial status
        */
        Status Initialize(ElemType data);

        /**
         * @brief Intializing a LinkedArrayListNode
         * @param a element put into the LinkedArrayListNode
         * @return the Initial status
        */
        Status Initialize(ElemType ctor(int));

        /**
         * @brief Insert an element from the begginning
         * @param data the element to insert
         * @return the push status
        */
        Status Push_Front(ElemType data);

        /**
         * @brief Insert an element from the end
         * @param data the element tp insert
         * @return the push status
        */
        Status Push_Back(ElemType data);

        /**
         * @brief Remove an element from the begginning
         * @return the pop status
        */
        Status Pop_Front();

        /**
         * @brief remove an element from the end
         * @return the pop status
        */
        Status Pop_Back();

        /**
         * @brief insert an element from the specified location
         * @return the insert status
        */
        Status Insert(int index, ElemType data);

        /**
         * @brief Remove an element from the specified location
         * @return the erase status
        */
        Status Erase(int index);

        /**
         * @brief sort array 
         * @param start where sorts starts
         * @param end where sorts ends
         * @param compare a function of comparison
         * @param mode sort mode ,initialize to stlsort
         * @return status of sort, succeed is true
        */
        Status Sort(int start, int end, bool compare(ElemType, ElemType), SortMode mode = stlsort);
       
        /**
         * @brief remove repetitive elements
         * @param start where the function starts to work
         * @param end where the function ends
         * @param compare a function of comparison,initialize to cn_sunist_datastructure_algorithm::memcompare
         * @return status of unique, succeed is true
        */
        Status Unique(int start, int end, bool compare(ElemType, ElemType) = cn_sunist_datastructure_algorithm::memcompare);

        /**
         * @brief exchange two elements at a specified location
         * @param index_a the index of one of the elements
         * @param index_b the index of the other element
         * @return status of swap, succeed is true
        */
        Status Swap(int index_a, int index_b);

        /**
         * @brief arrange parts of an array in reverse order
         * @param start where the reverse order starts
         * @param end where the reverse order ends
         * @return status of reverse, succeed is true
        */
        Status Reverse(int start, int end);

        /**
         * @brief find an element by subscript and return the element
         * @param index the subscript of the element to be found
         * @param isOriginal judge whether the index is original, intialize to false
         * @return the element to be found
        */
        ElemType& at(int index, bool isOriginal = false);

        /**
         * @brief reload the operator'[]'
         * @param index the subscript of the element to be found
         * @return the element to be found
        */
        ElemType& operator [] (int index);

        /**
         * @brief reload the operator'+='
         * @param data the element to be added from the end of the node
        */
        void operator += (ElemType data);

        /**
         * @brief reload the operatpr'-='
         * @param data the element to be remove from the node
        */
        void operator -= (ElemType data);
    };
}
// ================== CN_SUNIST_DATASTRUCTURE_PREVLIB_END ================= //










// ==================== CN_SUNIST_DATASTRUCTURE_LIBRARY =================== //
// ================= CN_SUNIST_DATASTRUCTURE_LIBRARY_START ================ //
/**
 * @Lastedit Sunist Chan
 * @Createdate 2020-10-08
 * @Authors Sunist Chan, CALC.
 * @Description The classes in sunist_chan_datastructure_library 
 * 
 * 这是scl库的正式命名空间，所有scl库的类都封装在本命名空间内
 */
namespace cn_sunist_datastructure_library {
    template<typename ElemType> 
    class LinkedList {
    private:
        cn_sunist_datastructure_prevlib::LinkedListNode<ElemType> *head;
        cn_sunist_datastructure_prevlib::LinkedListNode<ElemType> *rear;
        int length;

        /**
         * @brief to find the index-th Node in this LinkedListNode
         * @param index the index which want to find
         * @return the ptr of index-th LinkedListNode
         */
        cn_sunist_datastructure_prevlib::LinkedListNode<ElemType> *at(int index);

    public:
        /**
         * @brief the constructor of LinkedList
         */
        LinkedList<ElemType> ();

        /**
         * @brief the length of LinkedList
         * @return the length of LinkedList
         */
        int Length();

        /**
         * @brief if the LinkedList is empty
         * @return if empty, return true
         */
        bool Empty();

        /**
         * @brief to push a element at the front of LinkedList
         * @param data the pushed element
         * @return the push status
         */
        Status Push_Front(ElemType data);

        /**
         * @brief to push a element at the back of LinkedList
         * @param data the pushed element
         * @return the push status
         */
        Status Push_Back(ElemType data);

        /**
         * @brief to remove a element at the front of LinkedList
         * @return the remove status
         */
        Status Pop_Front();

        /**
         * @brief to remove a element at the back of LinkedList
         * @return the remove status
         */
        Status Pop_Back();

        /**
         * @brief add a new LinkedListNode from the specified place of the LinkedList
         * @return the insert status
        */
        Status Insert(int index, ElemType data);

        /**
         * @brief remove a LinkedListNode from the sepcified place of the LinkedList
         * @param index the order of the LinkedListNode
         * @param data the data stored in the LinkedListNode
         * @return the erase status
        */
        Status Erase(int index);

        /**
         * @brief sort the LinkedList
         * @param start where sort starts
         * @param end where sort ends
         * @param compare a function of comparison 
         * @return the sort status
        */
        Status Sort(int start, int end, bool compare(ElemType, ElemType));

        /**
         * @brief exchange two LinkedListNodes' order of the LinkedList
         * @param index_a the order of the one of the LinkedListNodes
         * @param index_b the order of the other LinkedListNode
         * @return the swap status
        */
        Status Swap(int index_a, int index_b);

        /**
         * @brief remove the same LinkedListNodes from the LinkedList
         * @param start where traversal starts
         * @param end where traversal ends
         * @param compare a function of comparison, initialize to cn_sunist_datastructure_algorithm::memcompare
         * @return the unique status
        */
        Status Unique(int start, int end, bool compare(ElemType, ElemType)=cn_sunist_datastructure_algorithm::memcompare);

        /**
         * @brief arrange a part of a LinkedList in reverse order
         * @param start where arrangement starts
         * @param end where arrangement ends
         * @return the reverse status
        */
        Status Reverse(int start, int end);

        /**
         * @brief reload the operator'[]'
         * @param index the order of the LinkedListNode
         * @return the data in LinkedListNode
        */
        ElemType& operator [] (int index);
    };

    template<typename ElemType> 
    class LinkedArrayList {
    private:
        int usedSize;
        int defaultNodeSize;
        ElemType nullemt;
        cn_sunist_datastructure_prevlib::LinkedArrayListNode<ElemType>* head;
        cn_sunist_datastructure_prevlib::LinkedArrayListNode<ElemType>* mid;
        cn_sunist_datastructure_prevlib::LinkedArrayListNode<ElemType>* rear;
        
        cn_sunist_datastructure_prevlib::LinkedArrayListNode<ElemType>* at(int index);

        /**
         * @brief find the specified element in a LinkedArrayListNode
         * @param index the subscript of the element to be found
         * @return the element
        */
        ElemType& atelem(int index);

        /**
         * @brief sort the LinkedArrayList
         * @param start where sort starts
         * @param end where sort ends
         * @param compare a function of comparison
        */
        void quick_Sort(int start, int end, bool compare(ElemType, ElemType));

    public:
        /**
         * @brief construct a LinkedArrayList
         * @param defaultsize the defaultsize, initialize to 20
        */
        LinkedArrayList<ElemType>(int defaultsize = 20);

        /**
         * @brief initialize a LinkedArrayList
         * @param data the data in the LinkedArrayListNode of the LinkedArrayList
        */
        Status Initialize(ElemType data);

        /**
         * @brief initialize a LinkedArrayList
         * @param ctor(int) the data in the LinkedArrayListNode of the LinkedArrayList
        */
        Status Initialize(ElemType ctor(int));

        /**
         * @brief the data stored in the head LinkedArrayListNode from the LinkedArrayList
         * @return the data in the head LinkedArrayListNode
        */
        ElemType Head();

        /**
         * @brief the data stored in the rear LinkedArrayListNode from the LinkedArrayList
         * @return the data in the rear LinkedArrayListNode
        */
        ElemType Rear();

        /**
         * @brief the stored length of the LinkedArrayList
         * @return the usedsize of the LinkedArrayList
        */
        int Length();

        /**
         * @brief the defaultsize of the LinkedArrayList
         * @return the defaultNodeSize of the LinkedArrayList
        */
        int DefaultSize();

        /**
         * @brief judge whether the LinkedArrayList is empty
         * @return if empty, return true
        */
        bool Empty();

        /**
         * @brief to push a element at the beginning of LinkedArrayList
         * @param data the data
         * @return the push status
        */
        Status Push_Front(ElemType data);

        /**
         * @brief to push a element at the beginning of LinkedArrayList
         * @param data the data
         * @return the push status
        */
        Status Push_Front(ElemType* dataArr, int len);

        /**
         * @brief to push a element at the beginning of LinkedArrayList
         * @param dataArr the data array in the LinkedArrayListNode
         * @param len the length of the data array
         * @return the push status
        */
        Status Push_Front(ElemType* dataArr, int start, int end);

        /**
         * @brief to push a data array at the beginning of LinkedArrayList
         * @param dataArr the data array in the LinkedArrayListNode
         * @param start where push starts
         * @param end where push ends
         * @return the push status
        */
        Status Push_Front(LinkedArrayList<ElemType> list);

        /**
         * @brief to push a LinkedArrayList at the beginning of LinkedArrayList
         * @param list a LinkedArrayList
         * @return the push status
        */
        Status Push_Front(LinkedArrayList<ElemType> list, int start, int end);

        /**
         * @brief to push a LinkedArrayList at the beginning of LinkedArrayList
         * @param list a LinkedArrayList
         * @param start where push starts
         * @param end where push ends
         * @return the push status
        */
        Status Push_Back(ElemType data);

        /**
         * @brief to push an element at the back of LinkedArrayList
         * @param data the data
         * @return the push status
        */
        Status Push_Back(ElemType* dataArr, int len);

        /**
         * @brief to push a data array at the back of LinkedArrayList
         * @param dataArr the data array in LinkedArrayListNode
         * @param len the length of dataArr
         * @return the push status
        */
        Status Push_Back(ElemType* dataArr, int start, int end);

        /**
         * @brief to push a element at the back of LinkedArrayList
         * @param dataArr the data array in the LinkedArrayListNode
         * @param start where push starts
         * @param end where push ends
         * @return the push status
        */
        Status Push_Back(LinkedArrayList<ElemType> list);

        /**
         * @brief to push a element at the back of LinkedArrayList
         * @param list the LinkedArrayList
         * @return the push status
        */
        Status Push_Back(LinkedArrayList<ElemType> list, int start, int end);

        /**
         * @brief insert an element at the specified place of the LinkedArrayList
         * @param index the subscipt of the place
         * @param data the data
         * @return the insert status
        */
        Status Insert(int index, ElemType data);

        /**
         * @brief insert a data array at the specified place of the LinkedArrayList
         * @param index the subscipt of the place
         * @param dataArr the data array
         * @param len the length of the data array
         * @return the insert status
        */
        Status Insert(int index, ElemType* dataArr, int len);

        /**
         * @brief insert an data array at the specified place of the LinkedArrayList
         * @param index the subscipt of the place
         * @param dataArr the data array
         * @param len the length of the data array
         * @return the insert status
        */
        Status Insert(int index, ElemType* dataArr, int start, int end);

        /**
         * @brief insert a data array at the specified place of the LinkedArrayList
         * @param index the subscipt of the place
         * @param dataArr the data array
         * @param start where insertion starts
         * @param end where insertion ends
         * @return the insert status
        */
        Status Insert(int index, LinkedArrayList<ElemType> list);

        /**
         * @brief insert a LinkedArrayList at the specified place of the LinkedArrayList
         * @param index the subscipt of the place
         * @param list the LinkedArrayList
         * @return the insert status
        */
        Status Insert(int index, LinkedArrayList<ElemType> list, int start, int end);

        /**
         * @brief remove an element at the specified place of the LinkedArrayList
         * @param index the subscript of the place
         * @return the erase status
        */
        Status Erase(int index);

        /**
         * @brief remove an array at the specified place of the LinkedArrayList
         * @param start where erasing starts
         * @param end where erasing ends
         * @return the erase status
        */
        Status Erase(int start, int end);

        /**
         * @brief pop an array at the specified place of the LinkedArrayList
         * @param len the length of the array
         * @return the pop status
        */
        Status Pop_Front(int len = 1);

        /**
         * @brief pop an array at the specified place of the LinkedArrayList
         * @param len the length of the array
         * @return the pop status
        */
        Status Pop_Back(int len = 1);

        /**
         * @brief sort the LinkedArrayList
         * @param start where sorts starts
         * @param end where sorts ends
         * @param compare a function of comparison
         * @param mode the sort mode, initialize to stlsort
         * @return the sort status
        */
        Status Sort(int start, int end, bool compare(ElemType, ElemType), SortMode mode = stlsort);

        /**
         * @brief remove the same LinkedArrayListNode in LinkedArrayList
         * @param start where to start traversing
         * @param end where to end traversing
         * @param compare a function of comparison, initialize to cn_sunist_datastructure_algorithm::memcompare
         * @param sorted whether the LinkedArrayList is sorted, initialize to flase
         * @return the unique status
        */
        Status Unique(int start, int end, bool compare(ElemType, ElemType) = cn_sunist_datastructure_algorithm::memcompare, bool sorted = false);

        /**
         * @brief swap two element in the LinkedArrayList
         * @param index_a the subscipt of the one of the elements
         * @param index_b the subscipt of the other element
         * @return the swap status
        */
        Status Swap(int index_a, int index_b);

        /**
         * @brief reverse the LinkedArrayList
         * @param start where to start traversing
         * @param end where to end traversing
         * @return the reverse status
        */
        Status Reverse(int start, int end);

        /**
         * @brief reload the operator'[]'
         * @param index the subscript of the element
         * @return the element
        */
        ElemType& operator [] (int index);
    };

    template<typename ElemType> 
    class ArrayList {
    private:
        ElemType NullNode;
        ElemType* Data;
        int definesize;

    public:
        /**
         * @brief the construction of arraylist
         * @param size the size of the arraylist, a int param, the default value is 0.
         */
        ArrayList<ElemType>(int size = 0);

        /**
         * @brief the copy construction of arraylist
         * @param another the another arraylist
         */
        ArrayList<ElemType>(const ArrayList<ElemType>& another);

        /**
         * @brief redefine the size of arraylist
         * @param size the new size of this arraylist
         * @return the resize status, success is true
         */
        bool Resize(int size);

        /**
         * @brief the define size of the arraylist
         * @return the define size of the arraylist
         */
        int Size();

        /**
         * @brief to show if this arraylist is empty
         * @return if empty, return true
         */
        bool Empty();

        /**
         * @brief to show the head ptr of this arraylist
         * @return the head ptr
         */
        ElemType* Head();

        /**
         * @brief to show the end ptr of this arraylist
         * @return the end ptr
         */
        ElemType* End();

        /**
         * @brief add a new element at the front of this arraylist
         * @param data the new element
         * @return the push status, success is true
         */
        bool Push_Front(ElemType data);

        /**
         * @brief add a new element at the back of this arraylist
         * @param data the new element
         * @return the push status, success is true
         */
        bool Push_Back(ElemType data);

        /**
         * @brief delete the frist element of this arraylist
         * @return the delete status, success is true
         */
        bool Pop_Front();

        /**
         * @brief delete the last element of this arraylist
         * @return the delete status, succeed is true
         */
        bool Pop_Back();

        /**
         * @brief insert a element as a index
         * @param index the index of insert element
         * @param data the insert element
         * @return the insert status, succeed is true
         */
        bool Insert(int index, ElemType data);

        /**
         * @brief insert elements from start_index
         * @param start_index the start index of the insert element
         * @param data the elements
         * @param len the length of elements
         * @return the insert status, succeed is true
         */
        bool Insert(int start_index, ElemType* data, int len);

        /**
         * @brief insert another arraylist to this arraylist start from index
         * @param index the start index
         * @param another the another arraylist
         * @return the insert status, succeed is true
         */
        bool Insert(int index, ArrayList<ElemType> another);

        /**
         * @brief delete the index-th element
         * @param index the index of the delete element
         * @return the delete status, succeed is true
         */
        bool Erase(int index);

        /**
         * @brief delete the elements from start_index to end_index
         * @param start_index the start index of the elements
         * @param end_index the end index of the elements
         * @return the delete status, succeed is true
         */
        bool Erase(int start_index, int end_index);

        /**
         * @brief clear the arraylist as NullNode from start_index to end_index
         * @param start_index the start index of the clear elements, default value is 0
         * @param end_index the end index of the clear elements, default value is size()-1
         * @return the clear status, succeed is true
         */
        bool Clear(int start_index, int end_index);

        /**
         * @brief to sort the elements in arraylist from start_index to end_index
         * @param compare the compare function, a bool type, ATTENTION: QUICKSORT MUST USE EQUAL
         * @param start_index the start index
         * @param end_index the end index
         * @param mode the SortMode, default mode is stlsort
         * @return the sort status, succeed is true
         */
        bool Sort(bool compare(ElemType, ElemType), ElemType start_index, ElemType end_index, SortMode mode = stlsort);

        /**
         * @brief to reverse the arraylist from start_index to end_index
         * @param start_index the start index of the elements, default value is 0
         * @param end_index the end index of the elements, default value is size()-1
         * @return the reverse status, succeed is true
         */
        bool Reverse(int start_index, int end_index);

        /**
         * @brief delete the same elements in arraylist with compare function from start_index to end_index
         * @param compare the compare function, a bool type
         * @param start_index the start index of the elements
         * @param end_index the end index of the elements
         * @return the number of the same elements
         */
        int Unique(int start_index, int end_index, bool compare(ElemType, ElemType) = cn_sunist_datastructure_algorithm::memcompare);

        /**
         * @brief to swap the index_a-th element and index_b-th element
         * @param index_a the index of one element
         * @param index_b the index of the another element
         * @return the swap status, succeed is true
         */
        bool Swap(int index_a, int index_b);

        /**
         * @brief to locate the index of a element
         * @param compare the compare function
         * @return the index of the element
         */
        int Locate(bool compare(ElemType));

        /**
         * @brief merge another arraylist to this arraylist
         * @param another the another arraylist
         * @return the merge status, succeed is true
         */
        bool Merge(ArrayList<ElemType> another);

        /**
         * @brief to union another arraylist
         * @param another the another arraylist
         * @return the union status, succeed is true
         */
        bool Union(ArrayList<ElemType> another, bool cmp(ElemType, ElemType) = cn_sunist_datastructure_algorithm::memcompare);

        /**
         * @brief merge this arraylist and another arraylist
         * @param another the another arraylist
         * @return the merged result
         */
        ArrayList<ElemType> operator + (ArrayList<ElemType> another);

        /**
         * @brief delete the elements which another arraylist included
         * @param another the another arraylist
         * @param compare the compare function
         * @return the deleted result
         */
        ArrayList<ElemType> operator - (ArrayList<ElemType> another);

        /**
         * @brief use arraylist as array
         * @param index the index of the array
         * @return the index-th element of this arraylist
         */
        ElemType& operator [] (int index);

        /**
         * @brief merge this arraylist and another arraylist
         * @param another the another arraylist
         */
        void operator += (ArrayList<ElemType> another);

        /**
         * @brief delete the elements which another arraylist included
         * @param another the another arraylist
         */
        void operator -= (ArrayList<ElemType> another);
    };

    template<typename ElemType> 
    class LinearSet {
    private:
        int DefaultSize;
        LinkedArrayList<ElemType> list;

    public:
        /**
         * @brief the constructor of LinearSet
         * @param defaultNodeSize the size of the LinearSet, a int param, the default value is 10
        */
        LinearSet<ElemType> (int defaultNodeSize=10);

        /**
         * @brief  set a LinkedArrayList into the LinearSet
         * @param list the LinkedArrayList
         * @return the set status
        */
        Status Set(LinkedArrayList<ElemType> list);

        /**
         * @brief get the LinkedArrayList from the LinearSet
         * @return the get status
        */
        LinkedArrayList<ElemType>& Get();

        /**
         * @brief the union of two LinkedArrayList
         * @param set the LinearSet 
         * @param cmp a function of comparison
         * @return a new LinearSet
        */
        LinearSet<ElemType>& Add (LinearSet<ElemType> set, bool cmp(ElemType, ElemType));

        /**
         * @brief the difference between two LinkedArrayList
         * @param set the LinearSet
         * @param cmp a function of comparison
         * @return a new LinearSet
        */
        LinearSet<ElemType>& Div (LinearSet<ElemType> set, bool cmp(ElemType, ElemType));

        /**
         * @brief the Intersection of two LinkedArrayList
         * @param set the LinearSet
         * @param cmp a function of comparison
         * @return a new LinearSet
        */
        LinearSet<ElemType>& Meg (LinearSet<ElemType> set, bool cmp(ElemType, ElemType));

        /**
         * @brief the complement of two LinkedArrayList
         * @param set the LinearSet to be added
         * @param cmp a function of comparison
         * @return a new LinearSet
        */
        LinearSet<ElemType>& Usf (LinearSet<ElemType> set, bool cmp(ElemType, ElemType));

        LinearSet<ElemType>& operator + (LinearSet<ElemType> set); // 并
        LinearSet<ElemType>& operator - (LinearSet<ElemType> set); // 差
        LinearSet<ElemType>& operator ^ (LinearSet<ElemType> set); // 交
        LinearSet<ElemType>& operator & (LinearSet<ElemType> set); // 补
    };

    template<typename ElemType> 
    class LinkedStack {
    private:
        LinkedList<ElemType> data;
        int length;
        cn_sunist_datastructure_prevlib::LinkedListNode<ElemType> *top;

    public:
        /**
         * @brief the constuctor of th LinkedStack
        */
        LinkedStack<ElemType> ();

        /**
         * @brief to show the length of the LinkedStack
        */
        int Length();

        /**
         * @brief to judge whether the LinkedStack is empty
         * @return if is empty, return true
        */
        bool Empty();

        /**
         * @brief to add an element from the end of  the LinkedStack
         * @param data the data
         * @return the push status
        */
        Status Push(ElemType data);

        /**
         * @brief to delete an element from the end of the LinkedStack
         * @return the pop status
        */
        Status Pop();

        /**
         * @brief to remove all elements from the LinkedStack
         * @return the status of clear
        */
        Status Clear();

        /**
         * @brief to show the last element of the LinkedStack
         * @return the element
        */
        ElemType Top();
    };

    template<typename ElemType> 
    class ArrayStack {
    private:
        ArrayList<ElemType> data;
        int length;

    public:
        /**
         * @brief the constuctor of the ArrayStack
        */
        ArrayStack<ElemType> ();

        /**
         * @brief to show the length of the ArrayStack
         * @return the length of the ArrayStack
        */
        int Length();

        /**
         * @brief to judge whether the ArrayStack is empty
         * @return if is empty, return true
        */
        bool Empty();

        /**
         * @brief to add an element from the end of the ArrayStack
         * @return the push status
        */
        Status Push(ElemType data);

        /**
         * @brief to remove an element from the end of the ArrayStack
         * @return the pop status
        */
        Status Pop();

        /**
         * @brief to remove all elements of the ArrayStack
         * @return the clear status
        */
        Status Clear();

        /**
         * @brief to show  the last element of the ArrayStack
         * @return the element
        */
        ElemType Top();
    };

    template<typename ElemType> class LinkedQueue {
    private:
        LinkedList<ElemType> data;
        int length;

    public:
        /**
         * @brief the constructor of the LinkedQueue
        */
        LinkedQueue<ElemType> ();

        /**
         * @brief to show the length of the LinkedQueue
         * @return the length of the LinkedQueue
        */
        int Length();

        /**
         * @brief to judge whether the LinkedQueue is empty
         * @return if is empty, return true
        */
        bool Empty();

        /**
        * @brief to add an element from the end of the LinkedQueue
        * @param data the element
        * @return the push status
       */
        Status Push(ElemType data);

        /**
         * @brief to remove an element from the end of the LinkedQueue
         * @return the pop status
        */
        Status Pop();

        /**
         * @brief to remove all elements of the LinkedQueue
         * @return the clear status
        */
        Status Clear();

        /**
         * @brief to show the first element of the LinkedQueue
         * @return the element
        */
        ElemType Front();

        /**
         * @brief to show the last element of the LinkedQueue
         * @return the element
        */
        ElemType Back();
    };

    template<typename ElemType> 
    class ArrayQueue {
    private:
        ArrayList<ElemType> data;
        int length;

    public:
        /**
         * @brief the constructor of the ArrayQueue
        */
        ArrayQueue<ElemType> ();

        /**
         * @brief to show the length of the ArrayQueue
         * @return the length of the ArrayQueue
        */
        int Length();

        /**
         * @brief to judge whether the ArrayQueue id empty
         * @return if is empty, return true
        */
        bool Empty();

        /**
        * @brief to add an element from the end of the ArrayQueue
        * @param data the element
        * @return the push status
       */
        Status Push(ElemType data);

        /**
         * @brief to remove an element from the end of the ArrayQueue
         * @return the pop status
        */
        Status Pop();

        /**
         * @brief to remove all elements of the ArrayQueue
         * @return the clear status
        */
        Status Clear();

        /**
         * @brief to show the first element of the ArrayQueue
         * @return the element
        */
        ElemType Front();

        /**
         * @brief to show the last element of the ArrayQueue
         * @return the element
        */
        ElemType Back();
    };
}
// ================== CN_SUNIST_DATASTRUCTURE_LIBRARY_END ================= //



#endif //DATA_STRUCTURE_EXPERIMENT_SCL_H
